<!DOCTYPE html>
<html lang="zh-CN">
    <head>
        <meta charset="utf-8">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="robots" content="noodp" />
        <title>通过阅读Redis源码简单实现跳表 - L_B__</title><meta name="referrer" content="no-referrer">
<meta name="description" content="通过阅读Redis源码简单实现跳表"><meta property="og:title" content="通过阅读Redis源码简单实现跳表" />
<meta property="og:description" content="通过阅读Redis源码简单实现跳表" />
<meta property="og:type" content="article" />
<meta property="og:url" content="https://acking-you.github.io/posts/%E9%98%85%E8%AF%BBredis%E6%BA%90%E7%A0%81%E5%AE%9E%E7%8E%B0%E8%B7%B3%E8%A1%A8/" /><meta property="og:image" content="https://acking-you.github.io/logo.png"/><meta property="article:section" content="posts" />
<meta property="article:published_time" content="2022-03-19T00:00:00+00:00" />
<meta property="article:modified_time" content="2022-03-19T00:00:00+00:00" />

<meta name="twitter:card" content="summary_large_image"/>
<meta name="twitter:image" content="https://acking-you.github.io/logo.png"/>

<meta name="twitter:title" content="通过阅读Redis源码简单实现跳表"/>
<meta name="twitter:description" content="通过阅读Redis源码简单实现跳表"/>
<meta name="application-name" content="FeelIt">
<meta name="apple-mobile-web-app-title" content="FeelIt"><meta name="theme-color" content="#ffffff"><meta name="msapplication-TileColor" content="#da532c"><link rel="canonical" href="https://acking-you.github.io/posts/%E9%98%85%E8%AF%BBredis%E6%BA%90%E7%A0%81%E5%AE%9E%E7%8E%B0%E8%B7%B3%E8%A1%A8/" /><link rel="prev" href="https://acking-you.github.io/posts/%E5%AE%8F%E5%92%8C%E6%A8%A1%E6%9D%BF%E7%9A%84%E5%AF%B9%E6%AF%94%E9%A2%84%E7%BC%96%E8%AF%91%E5%92%8C%E7%BC%96%E8%AF%91%E7%9A%84%E8%BE%83%E9%87%8F/" /><link rel="next" href="https://acking-you.github.io/posts/%E5%88%A9%E7%94%A8string_view%E4%BC%98%E5%8C%96%E7%8E%B0%E4%BB%A3c&#43;&#43;%E8%AF%AD%E6%B3%95/" /><link rel="stylesheet" href="/css/page.min.css"><link rel="stylesheet" href="/css/home.min.css"><script type="application/ld+json">
    {
        "@context": "http://schema.org",
        "@type": "BlogPosting",
        "headline": "通过阅读Redis源码简单实现跳表",
        "inLanguage": "zh-CN",
        "mainEntityOfPage": {
            "@type": "WebPage",
            "@id": "https:\/\/acking-you.github.io\/posts\/%E9%98%85%E8%AF%BBredis%E6%BA%90%E7%A0%81%E5%AE%9E%E7%8E%B0%E8%B7%B3%E8%A1%A8\/"
        },"genre": "posts","keywords": "通过阅读Redis源码简单实现跳表","wordcount":  3749 ,
        "url": "https:\/\/acking-you.github.io\/posts\/%E9%98%85%E8%AF%BBredis%E6%BA%90%E7%A0%81%E5%AE%9E%E7%8E%B0%E8%B7%B3%E8%A1%A8\/","datePublished": "2022-03-19T00:00:00+00:00","dateModified": "2022-03-19T00:00:00+00:00","publisher": {
            "@type": "Organization",
            "name": "作者"},"author": {
                "@type": "Person",
                "name": "作者"
            },"description": "通过阅读Redis源码简单实现跳表"
    }
    </script></head><body data-header-desktop="auto" data-header-mobile="auto"><script>(window.localStorage && localStorage.getItem('theme') ? localStorage.getItem('theme') === 'dark' : ('auto' === 'auto' ? window.matchMedia('(prefers-color-scheme: dark)').matches : 'auto' === 'dark')) && document.body.setAttribute('theme', 'dark');</script>

        <div id="mask"></div><div class="wrapper"><header class="desktop" id="header-desktop">
    <div class="header-wrapper">
        <div class="header-title">
            <a href="/" title="L_B__">L_B__</a>
        </div>
        <div class="menu">
            <div class="menu-inner"><a class="menu-item" href="/posts/"> 文章 </a><a class="menu-item" href="/tags/"> 标签 </a><a class="menu-item" href="/categories/"> 分类 </a><span class="menu-item delimiter"></span><span class="menu-item search" id="search-desktop">
                        <input type="text" placeholder="搜索文章标题或内容..." id="search-input-desktop">
                        <a href="#" class="search-button search-toggle" id="search-toggle-desktop" title="搜索">
                            <i class="fas fa-search fa-fw"></i>
                        </a>
                        <a href="#" class="search-button search-clear" id="search-clear-desktop" title="清空">
                            <i class="fas fa-times-circle fa-fw"></i>
                        </a>
                        <span class="search-button search-loading" id="search-loading-desktop">
                            <i class="fas fa-spinner fa-fw fa-spin"></i>
                        </span>
                    </span><a href="javascript:void(0);" class="menu-item theme-switch" title="切换主题">
                    <i class="fas fa-adjust fa-fw"></i>
                </a>
            </div>
        </div>
    </div>
</header><header class="mobile" id="header-mobile">
    <div class="header-container">
        <div class="header-wrapper">
            <div class="header-title">
                <a href="/" title="L_B__">L_B__</a>
            </div>
            <div class="menu-toggle" id="menu-toggle-mobile">
                <span></span><span></span><span></span>
            </div>
        </div>
        <div class="menu" id="menu-mobile"><div class="search-wrapper">
                    <div class="search mobile" id="search-mobile">
                        <input type="text" placeholder="搜索文章标题或内容..." id="search-input-mobile">
                        <a href="#" class="search-button search-toggle" id="search-toggle-mobile" title="搜索">
                            <i class="fas fa-search fa-fw"></i>
                        </a>
                        <a href="#" class="search-button search-clear" id="search-clear-mobile" title="清空">
                            <i class="fas fa-times-circle fa-fw"></i>
                        </a>
                        <span class="search-button search-loading" id="search-loading-mobile">
                            <i class="fas fa-spinner fa-fw fa-spin"></i>
                        </span>
                    </div>
                    <a href="#" class="search-cancel" id="search-cancel-mobile">
                        取消
                    </a>
                </div><a class="menu-item" href="/posts/" title="">文章</a><a class="menu-item" href="/tags/" title="">标签</a><a class="menu-item" href="/categories/" title="">分类</a><div class="menu-item"><a href="javascript:void(0);" class="theme-switch" title="切换主题">
                    <i class="fas fa-adjust fa-fw"></i>
                </a>
            </div></div>
    </div>
</header><div class="search-dropdown desktop">
    <div id="search-dropdown-desktop"></div>
</div>
<div class="search-dropdown mobile">
    <div id="search-dropdown-mobile"></div>
</div><main class="main">
                <div class="container"><div class="toc" id="toc-auto">
            <h2 class="toc-title">目录</h2>
            <div class="toc-content" id="toc-content-auto"></div>
        </div><article class="page single" data-toc="disable"><div class="featured-image"><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/img_convert/8db816efd6abe83538c4d47108d9c840.png#pic_center"
        data-srcset="https://img-blog.csdnimg.cn/img_convert/8db816efd6abe83538c4d47108d9c840.png#pic_center, https://img-blog.csdnimg.cn/img_convert/8db816efd6abe83538c4d47108d9c840.png#pic_center 1.5x, https://img-blog.csdnimg.cn/img_convert/8db816efd6abe83538c4d47108d9c840.png#pic_center 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/img_convert/8db816efd6abe83538c4d47108d9c840.png#pic_center"
        title="通过阅读Redis源码简单实现跳表" /></div><div class="single-card" data-image="true"><h2 class="single-title animated flipInX">通过阅读Redis源码简单实现跳表</h2><div class="post-meta">
                <div class="post-meta-line"><span class="post-author"><a href="/" title="Author" rel=" author" class="author"><i class="fas fa-user-circle fa-fw"></i>作者</a></span>&nbsp;<span class="post-category">出版于  <a href="/categories/%E6%89%8B%E5%86%99%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/"><i class="far fa-folder fa-fw"></i>手写数据结构</a></span></div>
                <div class="post-meta-line"><span><i class="far fa-calendar-alt fa-fw"></i>&nbsp;<time datetime="2022-03-19">2022-03-19</time></span>&nbsp;<span><i class="fas fa-pencil-alt fa-fw"></i>&nbsp;约 3749 字</span>&nbsp;
                    <span><i class="far fa-clock fa-fw"></i>&nbsp;预计阅读 8 分钟</span>&nbsp;</div>
            </div>
            
            <hr><div class="details toc" id="toc-static"  data-kept="">
                    <div class="details-summary toc-title">
                        <span>目录</span>
                        <span><i class="details-icon fas fa-angle-right"></i></span>
                    </div>
                    <div class="details-content toc-content" id="toc-content-static"><nav id="TableOfContents">
  <ul>
    <li><a href="#什么是跳表">什么是跳表？</a></li>
    <li><a href="#正式实现">正式实现</a>
      <ul>
        <li><a href="#跳表的创建">跳表的创建</a></li>
        <li><a href="#insert插入元素">Insert插入元素</a></li>
        <li><a href="#delete删除元素">Delete删除元素</a></li>
      </ul>
    </li>
    <li><a href="#正式解题">正式解题</a></li>
  </ul>
</nav></div>
                </div><div class="content" id="content"><h2 id="什么是跳表">什么是跳表？</h2>
<p>想要弄清这个，可以查看一篇大佬的文章，把跳表分析的非常透彻，并且剖析了Redis源码，我这里只讲解不带span的Redis源码C++复现。（后续会有带span的完美Redis源码C++复刻）
<a href="http://zhangtielei.com/posts/blog-redis-skiplist.html" target="_blank" rel="noopener noreffer">大佬的讲解</a></p>
<p>如果想查看Redis源码的各位，可以点进这个链接<a href="https://github1s.com/redis/redis/blob/unstable/src/t_zset.c" target="_blank" rel="noopener noreffer">https://github1s.com/redis/redis/blob/unstable/src/t_zset.c</a></p>
<p><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/0d425d26b59049b5bef9be20ae2a14fd.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/0d425d26b59049b5bef9be20ae2a14fd.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/0d425d26b59049b5bef9be20ae2a14fd.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/0d425d26b59049b5bef9be20ae2a14fd.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/0d425d26b59049b5bef9be20ae2a14fd.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="skiplist图片" /></p>
<h2 id="正式实现">正式实现</h2>
<h3 id="跳表的创建">跳表的创建</h3>
<h4 id="redis实现">Redis实现</h4>
<blockquote>
<p>跳表结构：sds类型是Redis内部实现的字符串
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/24d1a120c9fd4a469b77b191c18c9bac.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/24d1a120c9fd4a469b77b191c18c9bac.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/24d1a120c9fd4a469b77b191c18c9bac.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/24d1a120c9fd4a469b77b191c18c9bac.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/24d1a120c9fd4a469b77b191c18c9bac.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/24d1a120c9fd4a469b77b191c18c9bac.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
</blockquote>
<blockquote>
<p>创建函数，这时前面定义的level[]类型的优势就体现出来了，在C中这个类型算是未完成的类型，所以需要根据你给它分配的内存来进行具体的使用，没有分配内存前，你可以sizeof(zskiplistNode);试一试，你会发现level不计内存！</p>
<p><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/88bcbce60e5847609e80b019dc86c3e8.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/88bcbce60e5847609e80b019dc86c3e8.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/88bcbce60e5847609e80b019dc86c3e8.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/88bcbce60e5847609e80b019dc86c3e8.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/88bcbce60e5847609e80b019dc86c3e8.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/88bcbce60e5847609e80b019dc86c3e8.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
</blockquote>
<blockquote>
<p>销毁函数</p>
<p><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/868794816e094687a6c279b319c00221.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/868794816e094687a6c279b319c00221.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/868794816e094687a6c279b319c00221.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/868794816e094687a6c279b319c00221.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/868794816e094687a6c279b319c00221.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/868794816e094687a6c279b319c00221.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
</blockquote>
<h4 id="cpp实现">cpp实现</h4>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">struct</span> <span class="nc">SkiplistNode</span> <span class="p">{</span>
    <span class="c1">// string ele; 此题不需要维护元素字段，所以舍去
</span><span class="c1"></span>    <span class="kt">double</span> <span class="n">score</span><span class="p">;</span>
    <span class="n">SkiplistNode</span> <span class="o">*</span><span class="n">backward</span><span class="p">;</span>
    <span class="k">struct</span> <span class="nc">SkiplistLevel</span> <span class="p">{</span>
        <span class="k">struct</span> <span class="nc">SkiplistNode</span> <span class="o">*</span><span class="n">forward</span><span class="p">;</span>
        <span class="c1">// unsigned long span;此题不需要维护跨度，所以省去
</span><span class="c1"></span>    <span class="p">}</span><span class="o">*</span> <span class="n">level</span><span class="p">;</span>
<span class="c1">//TODO 构造和析构
</span><span class="c1"></span>    <span class="n">SkiplistNode</span><span class="p">(</span><span class="kt">int</span> <span class="n">level</span><span class="p">,</span><span class="kt">double</span> <span class="n">score</span><span class="p">)</span><span class="o">:</span><span class="n">level</span><span class="p">(</span><span class="k">new</span> <span class="n">SkiplistLevel</span><span class="p">[</span><span class="n">level</span><span class="p">])</span>
            <span class="p">,</span><span class="n">score</span><span class="p">(</span><span class="n">score</span><span class="p">),</span><span class="n">backward</span><span class="p">(</span><span class="k">nullptr</span><span class="p">){}</span>
    <span class="o">~</span><span class="n">SkiplistNode</span><span class="p">(){</span>
        <span class="k">delete</span><span class="p">[]</span> <span class="n">level</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>
</code></pre></div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">class</span> <span class="nc">Skiplist</span> <span class="p">{</span>
    <span class="k">struct</span> <span class="nc">SkiplistNode</span> <span class="o">*</span><span class="n">header</span><span class="p">,</span> <span class="o">*</span><span class="n">tail</span><span class="p">;</span>
    <span class="kt">unsigned</span> <span class="kt">long</span> <span class="n">length</span><span class="p">;</span>   <span class="c1">//当前跳表中的元素个数
</span><span class="c1"></span>    <span class="kt">int</span> <span class="n">level</span><span class="p">;</span>              <span class="c1">//当前跳表中最大表的高度
</span><span class="c1"></span><span class="k">public</span><span class="o">:</span>
    <span class="cm">/**
</span><span class="cm">     * 构造函数和析构函数
</span><span class="cm">     */</span>
    <span class="n">Skiplist</span><span class="p">()</span><span class="o">:</span><span class="n">level</span><span class="p">(</span><span class="mi">1</span><span class="p">),</span><span class="n">length</span><span class="p">(</span><span class="mi">0</span><span class="p">),</span><span class="n">tail</span><span class="p">(</span><span class="k">nullptr</span><span class="p">){</span>
        <span class="n">header</span> <span class="o">=</span> <span class="k">new</span> <span class="n">SkiplistNode</span><span class="p">(</span><span class="n">Skiplist_MAXLEVEL</span><span class="p">,</span><span class="mi">0</span><span class="p">);</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">Skiplist_MAXLEVEL</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">header</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">j</span><span class="p">].</span><span class="n">forward</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">header</span><span class="o">-&gt;</span><span class="n">backward</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="o">~</span><span class="n">Skiplist</span><span class="p">(){</span>
        <span class="n">SkiplistNode</span><span class="o">*</span> <span class="n">node</span> <span class="o">=</span> <span class="n">header</span><span class="p">,</span> <span class="o">*</span><span class="n">next</span><span class="p">;</span>
        <span class="k">while</span><span class="p">(</span><span class="n">node</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">next</span> <span class="o">=</span> <span class="n">node</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">forward</span><span class="p">;</span>
            <span class="k">delete</span> <span class="n">node</span><span class="p">;</span>
            <span class="n">node</span> <span class="o">=</span> <span class="n">next</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
 <span class="p">};</span>
</code></pre></div><h3 id="insert插入元素">Insert插入元素</h3>
<h4 id="redis实现-1">Redis实现</h4>
<p><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/4597eff7b32e4cc795c953b2f5aa84b8.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/4597eff7b32e4cc795c953b2f5aa84b8.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/4597eff7b32e4cc795c953b2f5aa84b8.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/4597eff7b32e4cc795c953b2f5aa84b8.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/4597eff7b32e4cc795c953b2f5aa84b8.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/4597eff7b32e4cc795c953b2f5aa84b8.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
<h4 id="cpp实现-1">cpp实现</h4>
<blockquote>
<p>带span和ele的1:1还原</p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"> <span class="n">SkiplistNode</span><span class="o">*</span> <span class="n">Skiplist</span><span class="o">::</span><span class="n">Insert</span><span class="p">(</span><span class="kt">double</span>  <span class="n">score</span><span class="p">,</span><span class="k">const</span> <span class="n">string</span><span class="o">&amp;</span> <span class="n">ele</span><span class="p">){</span>
        <span class="n">SkiplistNode</span> <span class="o">*</span><span class="n">update</span><span class="p">[</span><span class="n">Skiplist_MAXLEVEL</span><span class="p">],</span> <span class="o">*</span><span class="n">x</span><span class="p">;</span>
        <span class="kt">unsigned</span> <span class="kt">int</span> <span class="n">rank</span><span class="p">[</span><span class="n">Skiplist_MAXLEVEL</span><span class="p">];</span>
        <span class="kt">int</span> <span class="n">i</span><span class="p">,</span><span class="n">level</span><span class="p">;</span>
<span class="c1">//TODO part1：找到需要插入位置的前一个跳表节点，顺便更新update数组（存储着经过路径中的每个层级最多走到了哪个节点(用于连接新节点的每个层级的forward和更新span)）和rank数组（存储着路径中经过的层级节点到header的长度）
</span><span class="c1"></span>        <span class="n">x</span> <span class="o">=</span> <span class="n">header</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">level</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">rank</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span> <span class="o">==</span> <span class="p">(</span><span class="k">this</span><span class="o">-&gt;</span><span class="n">level</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="o">?</span> <span class="mi">0</span> <span class="o">:</span> <span class="n">rank</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">];</span>
            <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="n">rank</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">&lt;&lt;</span><span class="n">endl</span><span class="p">;</span>
            <span class="k">while</span> <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span> <span class="o">&amp;&amp;</span>
                   <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="o">-&gt;</span><span class="n">score</span> <span class="o">&lt;</span> <span class="n">score</span> <span class="o">||</span>
                    <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="o">-&gt;</span><span class="n">score</span> <span class="o">==</span> <span class="n">score</span> <span class="o">&amp;&amp;</span>
                     <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="o">-&gt;</span><span class="n">ele</span><span class="o">&lt;</span><span class="n">ele</span><span class="p">)))</span>
            <span class="p">{</span>
                <span class="n">rank</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">span</span><span class="p">;</span>
                <span class="n">x</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span>
        <span class="p">}</span>

<span class="c1">//TODO 生成节点内存，如果随机生成的节点拥有的层级比当前最高的节点还高，则需要把update数组和rank数组中高于当前level的部分看作是前一个节点是header来更新
</span><span class="c1"></span>        <span class="n">level</span> <span class="o">=</span> <span class="n">RandomLevel</span><span class="p">();</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">level</span> <span class="o">&gt;</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">level</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
                <span class="n">rank</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
                <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">header</span><span class="p">;</span>
                <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">span</span> <span class="o">=</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">length</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="k">this</span><span class="o">-&gt;</span><span class="n">level</span> <span class="o">=</span> <span class="n">level</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">x</span> <span class="o">=</span> <span class="k">new</span> <span class="n">SkiplistNode</span><span class="p">(</span><span class="n">level</span><span class="p">,</span><span class="n">score</span><span class="p">,</span><span class="n">ele</span><span class="p">);</span>

<span class="c1">//TODO 连接操作，连接的同时把上一个节点的span给转移给我，如果该层级的上一个节点就紧挨着那么可直接转移，否则根据update[i]-&gt;level[i].span - (rank[0] - rank[i]);来更新，实际上也包含了前一种情况
</span><span class="c1"></span>        <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">level</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span> <span class="o">=</span> <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="p">;</span>
            <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span>

            <span class="cm">/* update span covered by update[i] as x is inserted here */</span>
            <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">span</span> <span class="o">=</span> <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">span</span> <span class="o">-</span> <span class="p">(</span><span class="n">rank</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">-</span> <span class="n">rank</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span>
            <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">span</span> <span class="o">=</span> <span class="p">(</span><span class="n">rank</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">-</span> <span class="n">rank</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
        <span class="p">}</span>

<span class="c1">//TODO 最后的善后操作，1.前面高于它的节点，会因为它的产生而使得它们的span+1. 2.更新backward指针，如果不是队尾则需要更新后面的backward，如果插入的是队尾，则更新tail指针 3.更新length
</span><span class="c1"></span>        <span class="cm">/**
</span><span class="cm">         * 更新插入的节点未能到达的元素的span+1
</span><span class="cm">         */</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="n">level</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">span</span><span class="o">++</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="cm">/**
</span><span class="cm">         * 更新backward，以及判断插入元素是否是队尾，如果是，则更新tail指针
</span><span class="cm">         */</span>
        <span class="n">x</span><span class="o">-&gt;</span><span class="n">backward</span> <span class="o">=</span> <span class="p">(</span><span class="n">update</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">==</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">header</span><span class="p">)</span> <span class="o">?</span> <span class="k">nullptr</span> <span class="o">:</span> <span class="n">update</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">forward</span><span class="p">)</span>
            <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">forward</span><span class="o">-&gt;</span><span class="n">backward</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span>
        <span class="k">else</span>
            <span class="k">this</span><span class="o">-&gt;</span><span class="n">tail</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span>
        <span class="k">this</span><span class="o">-&gt;</span><span class="n">length</span><span class="o">++</span><span class="p">;</span>
        <span class="k">return</span> <span class="n">x</span><span class="p">;</span>
    <span class="p">}</span>
</code></pre></div><blockquote>
<p>不带span和ele</p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp">    <span class="n">SkiplistNode</span><span class="o">*</span> <span class="n">Skiplist</span><span class="o">::</span><span class="n">Insert</span><span class="p">(</span><span class="kt">double</span>  <span class="n">score</span><span class="p">){</span>
        <span class="n">SkiplistNode</span> <span class="o">*</span><span class="n">update</span><span class="p">[</span><span class="n">Skiplist_MAXLEVEL</span><span class="p">],</span> <span class="o">*</span><span class="n">x</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">i</span><span class="p">,</span><span class="n">level</span><span class="p">;</span>
<span class="c1">//TODO part1：找到需要插入位置的前一个跳表节点，顺便更新update数组(存储着经过路径中的每个层级最多走到了哪个节点(用于连接新节点的每个层级的forward))
</span><span class="c1"></span>        <span class="n">x</span> <span class="o">=</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">header</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">level</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">while</span> <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="o">&amp;&amp;</span>
                   <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="o">-&gt;</span><span class="n">score</span> <span class="o">&lt;</span> <span class="n">score</span><span class="p">)</span>
            <span class="p">{</span>
                <span class="n">x</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span>
        <span class="p">}</span>
<span class="c1">//TODO 生成节点内存，如果随机生成的节点拥有的层级比当前最高的节点还高，则需要把update数组中高于当前level的部分看作是前一个节点是header来更新
</span><span class="c1"></span>        <span class="n">level</span> <span class="o">=</span> <span class="n">RandomLevel</span><span class="p">();</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">level</span> <span class="o">&gt;</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">level</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
                <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">header</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="k">this</span><span class="o">-&gt;</span><span class="n">level</span> <span class="o">=</span> <span class="n">level</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">x</span> <span class="o">=</span> <span class="k">new</span> <span class="n">SkiplistNode</span><span class="p">(</span><span class="n">level</span><span class="p">,</span><span class="n">score</span><span class="p">);</span>

<span class="c1">//TODO 连接操作
</span><span class="c1"></span>        <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">level</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span> <span class="o">=</span> <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="p">;</span>
            <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="cm">/**
</span><span class="cm">         * 更新backward，以及判断插入元素是否是队尾，如果是，则更新tail指针
</span><span class="cm">         */</span>
        <span class="n">x</span><span class="o">-&gt;</span><span class="n">backward</span> <span class="o">=</span> <span class="p">(</span><span class="n">update</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">==</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">header</span><span class="p">)</span> <span class="o">?</span> <span class="k">nullptr</span> <span class="o">:</span> <span class="n">update</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">forward</span><span class="p">)</span>
            <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">forward</span><span class="o">-&gt;</span><span class="n">backward</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span>
        <span class="k">else</span>
            <span class="k">this</span><span class="o">-&gt;</span><span class="n">tail</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span>
        <span class="k">this</span><span class="o">-&gt;</span><span class="n">length</span><span class="o">++</span><span class="p">;</span>
        <span class="k">return</span> <span class="n">x</span><span class="p">;</span>
    <span class="p">}</span>
</code></pre></div><h3 id="delete删除元素">Delete删除元素</h3>
<h4 id="redis实现-2">Redis实现</h4>
<blockquote>
<p>delete的helper函数</p>
<p><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/091b3f79fa8f4f84b54f050a129dd969.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/091b3f79fa8f4f84b54f050a129dd969.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/091b3f79fa8f4f84b54f050a129dd969.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/091b3f79fa8f4f84b54f050a129dd969.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/091b3f79fa8f4f84b54f050a129dd969.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/091b3f79fa8f4f84b54f050a129dd969.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
</blockquote>
<blockquote>
<p>正式delete</p>
<p><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/58342137d98543c490e9d2ce7c3b7de6.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/58342137d98543c490e9d2ce7c3b7de6.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/58342137d98543c490e9d2ce7c3b7de6.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/58342137d98543c490e9d2ce7c3b7de6.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/58342137d98543c490e9d2ce7c3b7de6.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/58342137d98543c490e9d2ce7c3b7de6.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
</blockquote>
<h4 id="cpp实现-2">cpp实现</h4>
<blockquote>
<p>1:1还原实现</p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp">    <span class="cm">/**
</span><span class="cm">     * 该函数处理传入的update数组，并更新删除x节点后的指针连接和span值
</span><span class="cm">     * @param zsl 需要处理的跳表
</span><span class="cm">     * @param x   需要删除的节点
</span><span class="cm">     * @param update 需要处理的的update数组
</span><span class="cm">     */</span>
    <span class="k">static</span> <span class="kt">void</span> <span class="n">Skiplist</span><span class="o">::</span><span class="n">DeleteNode</span><span class="p">(</span><span class="n">Skiplist</span> <span class="o">*</span><span class="n">zsl</span><span class="p">,</span> <span class="n">SkiplistNode</span> <span class="o">*</span><span class="n">x</span><span class="p">,</span> <span class="n">SkiplistNode</span> <span class="o">**</span><span class="n">update</span><span class="p">)</span> <span class="p">{</span>
        <span class="kt">int</span> <span class="n">i</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">zsl</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span> <span class="o">==</span> <span class="n">x</span><span class="p">)</span> <span class="p">{</span><span class="c1">//TODO 如果该层级的节点的后一个节点就是x节点，那么删除x节点后span会增加，forward要更新
</span><span class="c1"></span>                <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">span</span> <span class="o">+=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">span</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span>
                <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="p">;</span>
            <span class="p">}</span> <span class="k">else</span> <span class="p">{</span><span class="c1">//TODO 如果后一个节点不是x节点，那么就仅仅只是跨度上减少1而已
</span><span class="c1"></span>                <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">span</span> <span class="o">-=</span> <span class="mi">1</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="p">}</span>
        <span class="c1">//TODO 和之前的插入处理相同，如果删除的节点是末尾节点，则需要更新tail指针，如果不是，则需要更新backward指针
</span><span class="c1"></span>        <span class="k">if</span> <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">forward</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">forward</span><span class="o">-&gt;</span><span class="n">backward</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">backward</span><span class="p">;</span>
        <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
            <span class="n">zsl</span><span class="o">-&gt;</span><span class="n">tail</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">backward</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">while</span><span class="p">(</span><span class="n">zsl</span><span class="o">-&gt;</span><span class="n">level</span> <span class="o">&gt;</span> <span class="mi">1</span> <span class="o">&amp;&amp;</span> <span class="n">zsl</span><span class="o">-&gt;</span><span class="n">header</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">zsl</span><span class="o">-&gt;</span><span class="n">level</span><span class="o">-</span><span class="mi">1</span><span class="p">].</span><span class="n">forward</span> <span class="o">==</span> <span class="nb">NULL</span><span class="p">)</span>
            <span class="n">zsl</span><span class="o">-&gt;</span><span class="n">level</span><span class="o">--</span><span class="p">;</span>
        <span class="n">zsl</span><span class="o">-&gt;</span><span class="n">length</span><span class="o">--</span><span class="p">;</span>
    <span class="p">}</span>

    <span class="cm">/**
</span><span class="cm">     * 根据score和ele删除节点
</span><span class="cm">     * @param score 传入的分值标识
</span><span class="cm">     * @param ele  传入的元素字符串标识
</span><span class="cm">     * @param node  用于选择是否要传出node，而不是就地删除
</span><span class="cm">     * @return 0表示节点未找到，1表示删除处理成功
</span><span class="cm">     */</span>
    <span class="kt">int</span> <span class="n">Skiplist</span><span class="o">::</span><span class="n">Delete</span><span class="p">(</span> <span class="kt">double</span> <span class="n">score</span><span class="p">,</span> <span class="n">string</span> <span class="n">ele</span><span class="p">,</span> <span class="n">SkiplistNode</span> <span class="o">**</span><span class="n">node</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">SkiplistNode</span> <span class="o">*</span><span class="n">update</span><span class="p">[</span><span class="n">Skiplist_MAXLEVEL</span><span class="p">],</span> <span class="o">*</span><span class="n">x</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">i</span><span class="p">;</span>

        <span class="n">x</span> <span class="o">=</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">header</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">level</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">while</span> <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span> <span class="o">&amp;&amp;</span>
                   <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="o">-&gt;</span><span class="n">score</span> <span class="o">&lt;</span> <span class="n">score</span> <span class="o">||</span>
                    <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="o">-&gt;</span><span class="n">score</span> <span class="o">==</span> <span class="n">score</span> <span class="o">&amp;&amp;</span>
                     <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="o">-&gt;</span><span class="n">ele</span><span class="o">&lt;</span><span class="n">ele</span><span class="p">)))</span>
            <span class="p">{</span>
                <span class="n">x</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="cm">/**
</span><span class="cm">         * 我们可能有多个相同分数的元素，我们需要找到同时具有正确分数和对象的元素。
</span><span class="cm">         */</span>
        <span class="n">x</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">forward</span><span class="p">;</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">&amp;&amp;</span> <span class="n">score</span> <span class="o">==</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">score</span> <span class="o">&amp;&amp;</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">ele</span><span class="o">==</span><span class="n">ele</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">DeleteNode</span><span class="p">(</span><span class="k">this</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">update</span><span class="p">);</span><span class="c1">//TODO 处理update数组上的指针连接
</span><span class="c1"></span>            <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">node</span><span class="p">)</span><span class="c1">//TODO 如果外界不需要接住node来进行处理，则该node就地销毁，否则资源传出到外界
</span><span class="c1"></span>                <span class="k">delete</span> <span class="n">x</span><span class="p">;</span>
            <span class="k">else</span>
                <span class="o">*</span><span class="n">node</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span>
            <span class="k">return</span> <span class="mi">1</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="cm">/* not found */</span>
    <span class="p">}</span>
</code></pre></div><blockquote>
<p>仅包含score的还原</p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="cm">/**
</span><span class="cm"> * 删除节点后的处理过程
</span><span class="cm"> * @param zsl 需要处理的跳表
</span><span class="cm"> * @param x   需要删除的节点
</span><span class="cm"> * @param update 需要处理的update数组
</span><span class="cm"> */</span>
    <span class="k">static</span> <span class="kt">void</span> <span class="n">Skiplist</span><span class="o">::</span><span class="n">DeleteHelper</span><span class="p">(</span><span class="n">Skiplist</span> <span class="o">*</span><span class="n">zsl</span><span class="p">,</span> <span class="n">SkiplistNode</span> <span class="o">*</span><span class="n">x</span><span class="p">,</span> <span class="n">SkiplistNode</span> <span class="o">**</span><span class="n">update</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">assert</span><span class="p">(</span><span class="n">zsl</span><span class="o">!=</span> <span class="k">nullptr</span><span class="o">&amp;&amp;</span><span class="n">x</span><span class="o">!=</span> <span class="k">nullptr</span><span class="o">&amp;&amp;</span><span class="n">update</span><span class="o">!=</span> <span class="k">nullptr</span><span class="p">);</span>
        <span class="kt">int</span> <span class="n">i</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">zsl</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span> <span class="o">==</span> <span class="n">x</span><span class="p">)</span> <span class="p">{</span>
                <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="p">}</span>
        <span class="c1">//TODO 和之前的插入处理相同，如果删除的节点是末尾节点，则需要更新tail指针，如果不是，则更新backward指针
</span><span class="c1"></span>        <span class="k">if</span> <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">forward</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">forward</span><span class="o">-&gt;</span><span class="n">backward</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">backward</span><span class="p">;</span>
        <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
            <span class="n">zsl</span><span class="o">-&gt;</span><span class="n">tail</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">backward</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="c1">//TODO 删除的节点可能是最高的高度，由于可能存在多个相同的高度，所以我们不能直接判断
</span><span class="c1"></span>        <span class="c1">// 可从头节点的forward指针是否为空来确认高度是否需要下降
</span><span class="c1"></span>        <span class="k">while</span><span class="p">(</span><span class="n">zsl</span><span class="o">-&gt;</span><span class="n">level</span> <span class="o">&gt;</span> <span class="mi">1</span> <span class="o">&amp;&amp;</span> <span class="n">zsl</span><span class="o">-&gt;</span><span class="n">header</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">zsl</span><span class="o">-&gt;</span><span class="n">level</span><span class="o">-</span><span class="mi">1</span><span class="p">].</span><span class="n">forward</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
            <span class="n">zsl</span><span class="o">-&gt;</span><span class="n">level</span><span class="o">--</span><span class="p">;</span>
        <span class="n">zsl</span><span class="o">-&gt;</span><span class="n">length</span><span class="o">--</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="cm">/**
</span><span class="cm">     * 根据score和ele删除节点
</span><span class="cm">     * @param score 传入的分值标识
</span><span class="cm">     * @param node  用于选择是否要传出node，而不是就地删除
</span><span class="cm">     * @return 0表示节点未找到，1表示删除处理成功
</span><span class="cm">     */</span>
    <span class="kt">int</span> <span class="n">Skiplist</span><span class="o">::</span><span class="n">Delete</span><span class="p">(</span> <span class="kt">double</span> <span class="n">score</span><span class="p">,</span><span class="n">SkiplistNode</span> <span class="o">**</span><span class="n">node</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">SkiplistNode</span> <span class="o">*</span><span class="n">update</span><span class="p">[</span><span class="n">Skiplist_MAXLEVEL</span><span class="p">],</span> <span class="o">*</span><span class="n">x</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">i</span><span class="p">;</span>
        <span class="cm">/**
</span><span class="cm">         * 查找并更新update数组
</span><span class="cm">         */</span>
        <span class="n">x</span> <span class="o">=</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">header</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">level</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">while</span> <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span> <span class="o">&amp;&amp;</span>
                   <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="o">-&gt;</span><span class="n">score</span> <span class="o">&lt;</span> <span class="n">score</span><span class="p">))</span>
            <span class="p">{</span>
                <span class="n">x</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="n">x</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">forward</span><span class="p">;</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">&amp;&amp;</span> <span class="n">score</span> <span class="o">==</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">score</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">DeleteHelper</span><span class="p">(</span><span class="k">this</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">update</span><span class="p">);</span><span class="c1">//TODO 处理update数组上的指针连接
</span><span class="c1"></span>            <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">node</span><span class="p">)</span><span class="c1">//TODO 如果外界不需要接住node来进行处理，则该node就地销毁，否则资源传出到外界
</span><span class="c1"></span>                <span class="k">delete</span> <span class="n">x</span><span class="p">;</span>
            <span class="k">else</span>
                <span class="o">*</span><span class="n">node</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span>
            <span class="k">return</span> <span class="mi">1</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="cm">/* not found */</span>
    <span class="p">}</span>
</code></pre></div><h2 id="正式解题">正式解题</h2>
<p><a href="https://leetcode-cn.com/problems/design-skiplist/submissions/" target="_blank" rel="noopener noreffer">题目链接</a></p>
<blockquote>
<p>前面的增删弄懂了，这个跳表的各种查找也就不在话下了，现在可以正式解题了。
效率还是比较nice的！
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/d502abcbcaa24cdbbfd45702fe037850.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_18,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/d502abcbcaa24cdbbfd45702fe037850.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_18%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/d502abcbcaa24cdbbfd45702fe037850.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_18%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/d502abcbcaa24cdbbfd45702fe037850.png?x-oss-process=image/watermark%2ctype_d3F5LXplbmhlaQ%2cshadow_50%2ctext_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=%2csize_18%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/d502abcbcaa24cdbbfd45702fe037850.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_18,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/d502abcbcaa24cdbbfd45702fe037850.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQysrKysrKysrKysrKysrKysrKys=,size_18,color_FFFFFF,t_70,g_se,x_16" /></p>
</blockquote>
<p>解题源码：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="cp">#define Skiplist_MAXLEVEL 32 </span><span class="cm">/* Should be enough for 2^64 elements */</span><span class="cp">
</span><span class="cp">#define Skiplist_P 0.25      </span><span class="cm">/* Skiplist P = 1/4 */</span><span class="cp">
</span><span class="cp"></span>
<span class="k">struct</span> <span class="nc">SkiplistNode</span> <span class="p">{</span>
    <span class="c1">// string ele; 此题不需要维护元素字段，所以舍去
</span><span class="c1"></span>    <span class="kt">double</span> <span class="n">score</span><span class="p">;</span>
    <span class="n">SkiplistNode</span> <span class="o">*</span><span class="n">backward</span><span class="p">;</span>
    <span class="k">struct</span> <span class="nc">SkiplistLevel</span> <span class="p">{</span>
        <span class="k">struct</span> <span class="nc">SkiplistNode</span> <span class="o">*</span><span class="n">forward</span><span class="p">;</span>
        <span class="c1">// unsigned long span;此题不需要维护跨度，所以省去
</span><span class="c1"></span>    <span class="p">}</span><span class="o">*</span> <span class="n">level</span><span class="p">;</span>

    <span class="n">SkiplistNode</span><span class="p">(</span><span class="kt">int</span> <span class="n">level</span><span class="p">,</span><span class="kt">double</span> <span class="n">score</span><span class="p">)</span><span class="o">:</span><span class="n">level</span><span class="p">(</span><span class="k">new</span> <span class="n">SkiplistLevel</span><span class="p">[</span><span class="n">level</span><span class="p">])</span>
            <span class="p">,</span><span class="n">score</span><span class="p">(</span><span class="n">score</span><span class="p">),</span><span class="n">backward</span><span class="p">(</span><span class="k">nullptr</span><span class="p">){}</span>
    <span class="o">~</span><span class="n">SkiplistNode</span><span class="p">(){</span>
        <span class="k">delete</span><span class="p">[]</span> <span class="n">level</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>


<span class="k">class</span> <span class="nc">Skiplist</span> <span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="k">struct</span> <span class="nc">SkiplistNode</span> <span class="o">*</span><span class="n">header</span><span class="p">,</span> <span class="o">*</span><span class="n">tail</span><span class="p">;</span>
    <span class="kt">unsigned</span> <span class="kt">long</span> <span class="n">length</span><span class="p">;</span>   <span class="c1">//当前跳表中的元素个数
</span><span class="c1"></span>    <span class="kt">int</span> <span class="n">level</span><span class="p">;</span>              <span class="c1">//当前跳表中最大表的高度
</span><span class="c1"></span><span class="k">private</span><span class="o">:</span>
<span class="cm">/**
</span><span class="cm"> *
</span><span class="cm"> * @return 返回随机产生的level高度
</span><span class="cm"> */</span>
    <span class="k">static</span> <span class="kt">int</span> <span class="n">RandomLevel</span><span class="p">()</span> <span class="p">{</span><span class="c1">//TODO 根据rand()和掩码相与得到对应的随机值(0,0xffff)来产生level
</span><span class="c1"></span>        <span class="kt">int</span> <span class="n">level</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
        <span class="k">while</span> <span class="p">((</span><span class="n">rand</span><span class="p">()</span><span class="o">&amp;</span><span class="mh">0xFFFF</span><span class="p">)</span> <span class="o">&lt;</span> <span class="p">(</span><span class="n">Skiplist_P</span> <span class="o">*</span> <span class="mh">0xFFFF</span><span class="p">))</span>
            <span class="n">level</span> <span class="o">+=</span> <span class="mi">1</span><span class="p">;</span>
        <span class="k">return</span> <span class="p">(</span><span class="n">level</span><span class="o">&lt;</span><span class="n">Skiplist_MAXLEVEL</span><span class="p">)</span> <span class="o">?</span> <span class="nl">level</span> <span class="p">:</span> <span class="n">Skiplist_MAXLEVEL</span><span class="p">;</span>
    <span class="p">}</span>
<span class="cm">/**
</span><span class="cm"> * 删除节点后的处理过程
</span><span class="cm"> * @param zsl 需要处理的跳表
</span><span class="cm"> * @param x   需要删除的节点
</span><span class="cm"> * @param update 需要处理的update数组
</span><span class="cm"> */</span>
    <span class="k">static</span> <span class="kt">void</span> <span class="nf">DeleteHelper</span><span class="p">(</span><span class="n">Skiplist</span> <span class="o">*</span><span class="n">zsl</span><span class="p">,</span> <span class="n">SkiplistNode</span> <span class="o">*</span><span class="n">x</span><span class="p">,</span> <span class="n">SkiplistNode</span> <span class="o">**</span><span class="n">update</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">assert</span><span class="p">(</span><span class="n">zsl</span><span class="o">!=</span> <span class="k">nullptr</span><span class="o">&amp;&amp;</span><span class="n">x</span><span class="o">!=</span> <span class="k">nullptr</span><span class="o">&amp;&amp;</span><span class="n">update</span><span class="o">!=</span> <span class="k">nullptr</span><span class="p">);</span>
        <span class="kt">int</span> <span class="n">i</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">zsl</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span> <span class="o">==</span> <span class="n">x</span><span class="p">)</span> <span class="p">{</span>
                <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="p">}</span>
        <span class="c1">//TODO 和之前的插入处理相同，如果删除的节点是末尾节点，则需要更新tail指针，如果不是，则更新backward指针
</span><span class="c1"></span>        <span class="k">if</span> <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">forward</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">forward</span><span class="o">-&gt;</span><span class="n">backward</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">backward</span><span class="p">;</span>
        <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
            <span class="n">zsl</span><span class="o">-&gt;</span><span class="n">tail</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">backward</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="c1">//TODO 删除的节点可能是最高的高度，由于可能存在多个相同的高度，所以我们不能直接判断
</span><span class="c1"></span>        <span class="c1">// 可从头节点的forward指针是否为空来确认高度是否需要下降
</span><span class="c1"></span>        <span class="k">while</span><span class="p">(</span><span class="n">zsl</span><span class="o">-&gt;</span><span class="n">level</span> <span class="o">&gt;</span> <span class="mi">1</span> <span class="o">&amp;&amp;</span> <span class="n">zsl</span><span class="o">-&gt;</span><span class="n">header</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">zsl</span><span class="o">-&gt;</span><span class="n">level</span><span class="o">-</span><span class="mi">1</span><span class="p">].</span><span class="n">forward</span> <span class="o">==</span> <span class="k">nullptr</span><span class="p">)</span>
            <span class="n">zsl</span><span class="o">-&gt;</span><span class="n">level</span><span class="o">--</span><span class="p">;</span>
        <span class="n">zsl</span><span class="o">-&gt;</span><span class="n">length</span><span class="o">--</span><span class="p">;</span>
    <span class="p">}</span>
<span class="k">public</span><span class="o">:</span>
    <span class="cm">/**
</span><span class="cm">     * 构造函数和析构函数
</span><span class="cm">     */</span>
    <span class="n">Skiplist</span><span class="p">()</span><span class="o">:</span><span class="n">level</span><span class="p">(</span><span class="mi">1</span><span class="p">),</span><span class="n">length</span><span class="p">(</span><span class="mi">0</span><span class="p">),</span><span class="n">tail</span><span class="p">(</span><span class="k">nullptr</span><span class="p">){</span>
        <span class="n">header</span> <span class="o">=</span> <span class="k">new</span> <span class="n">SkiplistNode</span><span class="p">(</span><span class="n">Skiplist_MAXLEVEL</span><span class="p">,</span><span class="mi">0</span><span class="p">);</span>
        <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">Skiplist_MAXLEVEL</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">header</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">j</span><span class="p">].</span><span class="n">forward</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">header</span><span class="o">-&gt;</span><span class="n">backward</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="o">~</span><span class="n">Skiplist</span><span class="p">(){</span>
        <span class="n">SkiplistNode</span><span class="o">*</span> <span class="n">node</span> <span class="o">=</span> <span class="n">header</span><span class="p">,</span> <span class="o">*</span><span class="n">next</span><span class="p">;</span>
        <span class="k">while</span><span class="p">(</span><span class="n">node</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">next</span> <span class="o">=</span> <span class="n">node</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">forward</span><span class="p">;</span>
            <span class="k">delete</span> <span class="n">node</span><span class="p">;</span>
            <span class="n">node</span> <span class="o">=</span> <span class="n">next</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="cm">/**
</span><span class="cm">     * 插入元素
</span><span class="cm">     * @param score  用于定位的score
</span><span class="cm">     * @param ele 存储的元素
</span><span class="cm">     * @return 被插入元素的指针
</span><span class="cm">     */</span>
    <span class="n">SkiplistNode</span><span class="o">*</span> <span class="nf">Insert</span><span class="p">(</span><span class="kt">double</span>  <span class="n">score</span><span class="p">){</span>
        <span class="n">SkiplistNode</span> <span class="o">*</span><span class="n">update</span><span class="p">[</span><span class="n">Skiplist_MAXLEVEL</span><span class="p">],</span> <span class="o">*</span><span class="n">x</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">i</span><span class="p">,</span><span class="n">level</span><span class="p">;</span>
<span class="c1">//TODO part1：找到需要插入位置的前一个跳表节点，顺便更新update数组(存储着经过路径中的每个层级最多走到了哪个节点(用于连接新节点的每个层级的forward))
</span><span class="c1"></span>        <span class="n">x</span> <span class="o">=</span> <span class="n">header</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">level</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">while</span> <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="o">&amp;&amp;</span>
                   <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="o">-&gt;</span><span class="n">score</span> <span class="o">&lt;</span> <span class="n">score</span><span class="p">)</span>
            <span class="p">{</span>
                <span class="n">x</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span>
        <span class="p">}</span>
<span class="c1">//TODO 生成节点内存，如果随机生成的节点拥有的层级比当前最高的节点还高，则需要把update数组中高于当前level的部分看作是前一个节点是header来更新
</span><span class="c1"></span>        <span class="n">level</span> <span class="o">=</span> <span class="n">RandomLevel</span><span class="p">();</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">level</span> <span class="o">&gt;</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">level</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
                <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">header</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="k">this</span><span class="o">-&gt;</span><span class="n">level</span> <span class="o">=</span> <span class="n">level</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">x</span> <span class="o">=</span> <span class="k">new</span> <span class="n">SkiplistNode</span><span class="p">(</span><span class="n">level</span><span class="p">,</span><span class="n">score</span><span class="p">);</span>

<span class="c1">//TODO 连接操作
</span><span class="c1"></span>        <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">level</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span> <span class="o">=</span> <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="p">;</span>
            <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="cm">/**
</span><span class="cm">         * 更新backward，以及判断插入元素是否是队尾，如果是，则更新tail指针
</span><span class="cm">         */</span>
        <span class="n">x</span><span class="o">-&gt;</span><span class="n">backward</span> <span class="o">=</span> <span class="p">(</span><span class="n">update</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">==</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">header</span><span class="p">)</span> <span class="o">?</span> <span class="k">nullptr</span> <span class="o">:</span> <span class="n">update</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">forward</span><span class="p">)</span>
            <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">forward</span><span class="o">-&gt;</span><span class="n">backward</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span>
        <span class="k">else</span>
            <span class="k">this</span><span class="o">-&gt;</span><span class="n">tail</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span>
        <span class="k">this</span><span class="o">-&gt;</span><span class="n">length</span><span class="o">++</span><span class="p">;</span>
        <span class="k">return</span> <span class="n">x</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="cm">/**
</span><span class="cm">     * 根据score和ele删除节点
</span><span class="cm">     * @param score 传入的分值标识
</span><span class="cm">     * @param node  用于选择是否要传出node，而不是就地删除
</span><span class="cm">     * @return 0表示节点未找到，1表示删除处理成功
</span><span class="cm">     */</span>
    <span class="kt">int</span> <span class="nf">Delete</span><span class="p">(</span> <span class="kt">double</span> <span class="n">score</span><span class="p">,</span><span class="n">SkiplistNode</span> <span class="o">**</span><span class="n">node</span> <span class="o">=</span> <span class="k">nullptr</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">SkiplistNode</span> <span class="o">*</span><span class="n">update</span><span class="p">[</span><span class="n">Skiplist_MAXLEVEL</span><span class="p">],</span> <span class="o">*</span><span class="n">x</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">i</span><span class="p">;</span>
        <span class="cm">/**
</span><span class="cm">         * 查找并更新update数组
</span><span class="cm">         */</span>
        <span class="n">x</span> <span class="o">=</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">header</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">level</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">while</span> <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span> <span class="o">&amp;&amp;</span>
                   <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="o">-&gt;</span><span class="n">score</span> <span class="o">&lt;</span> <span class="n">score</span><span class="p">))</span>
            <span class="p">{</span>
                <span class="n">x</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="n">update</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="n">x</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">forward</span><span class="p">;</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">x</span> <span class="o">&amp;&amp;</span> <span class="n">score</span> <span class="o">==</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">score</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">DeleteHelper</span><span class="p">(</span><span class="k">this</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">update</span><span class="p">);</span><span class="c1">//TODO 处理update数组上的指针连接
</span><span class="c1"></span>            <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">node</span><span class="p">)</span><span class="c1">//TODO 如果外界不需要接住node来进行处理，则该node就地销毁，否则资源传出到外界
</span><span class="c1"></span>                <span class="k">delete</span> <span class="n">x</span><span class="p">;</span>
            <span class="k">else</span>
                <span class="o">*</span><span class="n">node</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span>
            <span class="k">return</span> <span class="mi">1</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="cm">/* not found */</span>
    <span class="p">}</span>
    
<span class="c1">//本题的函数接口
</span><span class="c1"></span>    <span class="kt">bool</span> <span class="nf">search</span><span class="p">(</span><span class="kt">int</span> <span class="n">target</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
        <span class="kt">double</span> <span class="n">score</span> <span class="o">=</span> <span class="n">target</span><span class="p">;</span>
        <span class="n">SkiplistNode</span><span class="o">*</span> <span class="n">x</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">i</span><span class="p">;</span>
        <span class="n">x</span> <span class="o">=</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">header</span><span class="p">;</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">level</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">while</span> <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span> <span class="o">&amp;&amp;</span>
                   <span class="p">(</span><span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="o">-&gt;</span><span class="n">score</span> <span class="o">&lt;</span> <span class="n">score</span><span class="p">))</span>
            <span class="p">{</span>
                <span class="n">x</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">forward</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="p">}</span>
        <span class="k">auto</span> <span class="n">val</span> <span class="o">=</span> <span class="n">x</span><span class="o">-&gt;</span><span class="n">level</span><span class="p">[</span><span class="mi">0</span><span class="p">].</span><span class="n">forward</span><span class="p">;</span>
        <span class="k">if</span><span class="p">(</span><span class="n">val</span><span class="p">)</span>
            <span class="k">return</span> <span class="n">val</span><span class="o">-&gt;</span><span class="n">score</span><span class="o">==</span><span class="n">score</span><span class="p">;</span>
        <span class="k">return</span> <span class="nb">false</span><span class="p">;</span>
    <span class="p">}</span>

    <span class="kt">void</span> <span class="nf">add</span><span class="p">(</span><span class="kt">int</span> <span class="n">num</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">Insert</span><span class="p">(</span><span class="kt">double</span><span class="p">(</span><span class="n">num</span><span class="p">));</span>
    <span class="p">}</span>

    <span class="kt">bool</span> <span class="nf">erase</span><span class="p">(</span><span class="kt">int</span> <span class="n">num</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">return</span> <span class="n">Delete</span><span class="p">(</span><span class="kt">double</span><span class="p">(</span><span class="n">num</span><span class="p">));</span>
    <span class="p">}</span>
<span class="p">};</span>
</code></pre></div></div><div class="post-footer" id="post-footer">
    <div class="post-info"><div class="post-info-tag"><span><a href="/tags/%E9%80%9A%E8%BF%87%E9%98%85%E8%AF%BBredis%E6%BA%90%E7%A0%81%E7%AE%80%E5%8D%95%E5%AE%9E%E7%8E%B0%E8%B7%B3%E8%A1%A8/">通过阅读Redis源码简单实现跳表</a>
                </span></div><div class="post-info-line"><div class="post-info-mod">
                <span>更新于 2022-03-19</span>
            </div><div class="post-info-mod"></div>
        </div><div class="post-info-share">
            <span><a href="javascript:void(0);" title="分享到 Twitter" data-sharer="twitter" data-url="https://acking-you.github.io/posts/%E9%98%85%E8%AF%BBredis%E6%BA%90%E7%A0%81%E5%AE%9E%E7%8E%B0%E8%B7%B3%E8%A1%A8/" data-title="通过阅读Redis源码简单实现跳表" data-hashtags="通过阅读Redis源码简单实现跳表"><i class="fab fa-twitter fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Facebook" data-sharer="facebook" data-url="https://acking-you.github.io/posts/%E9%98%85%E8%AF%BBredis%E6%BA%90%E7%A0%81%E5%AE%9E%E7%8E%B0%E8%B7%B3%E8%A1%A8/" data-hashtag="通过阅读Redis源码简单实现跳表"><i class="fab fa-facebook-square fa-fw"></i></a><a href="javascript:void(0);" title="分享到 WhatsApp" data-sharer="whatsapp" data-url="https://acking-you.github.io/posts/%E9%98%85%E8%AF%BBredis%E6%BA%90%E7%A0%81%E5%AE%9E%E7%8E%B0%E8%B7%B3%E8%A1%A8/" data-title="通过阅读Redis源码简单实现跳表" data-web><i class="fab fa-whatsapp fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Line" data-sharer="line" data-url="https://acking-you.github.io/posts/%E9%98%85%E8%AF%BBredis%E6%BA%90%E7%A0%81%E5%AE%9E%E7%8E%B0%E8%B7%B3%E8%A1%A8/" data-title="通过阅读Redis源码简单实现跳表"><i class="fab fa-line fa-fw"></i></a><a href="javascript:void(0);" title="分享到 微博" data-sharer="weibo" data-url="https://acking-you.github.io/posts/%E9%98%85%E8%AF%BBredis%E6%BA%90%E7%A0%81%E5%AE%9E%E7%8E%B0%E8%B7%B3%E8%A1%A8/" data-title="通过阅读Redis源码简单实现跳表" data-image="https://img-blog.csdnimg.cn/img_convert/8db816efd6abe83538c4d47108d9c840.png#pic_center"><i class="fab fa-weibo fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Myspace" data-sharer="myspace" data-url="https://acking-you.github.io/posts/%E9%98%85%E8%AF%BBredis%E6%BA%90%E7%A0%81%E5%AE%9E%E7%8E%B0%E8%B7%B3%E8%A1%A8/" data-title="通过阅读Redis源码简单实现跳表" data-description="通过阅读Redis源码简单实现跳表"><i data-svg-src="/lib/simple-icons/icons/myspace.min.svg"></i></a><a href="javascript:void(0);" title="分享到 Blogger" data-sharer="blogger" data-url="https://acking-you.github.io/posts/%E9%98%85%E8%AF%BBredis%E6%BA%90%E7%A0%81%E5%AE%9E%E7%8E%B0%E8%B7%B3%E8%A1%A8/" data-title="通过阅读Redis源码简单实现跳表" data-description="通过阅读Redis源码简单实现跳表"><i class="fab fa-blogger fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Evernote" data-sharer="evernote" data-url="https://acking-you.github.io/posts/%E9%98%85%E8%AF%BBredis%E6%BA%90%E7%A0%81%E5%AE%9E%E7%8E%B0%E8%B7%B3%E8%A1%A8/" data-title="通过阅读Redis源码简单实现跳表"><i class="fab fa-evernote fa-fw"></i></a></span>
        </div></div><div class="post-nav"><a href="/posts/%E5%AE%8F%E5%92%8C%E6%A8%A1%E6%9D%BF%E7%9A%84%E5%AF%B9%E6%AF%94%E9%A2%84%E7%BC%96%E8%AF%91%E5%92%8C%E7%BC%96%E8%AF%91%E7%9A%84%E8%BE%83%E9%87%8F/" class="prev" rel="prev" title="宏和模板的对比——预编译和编译的较量"><i class="fas fa-angle-left fa-fw"></i>Previous Post</a>
            <a href="/posts/%E5%88%A9%E7%94%A8string_view%E4%BC%98%E5%8C%96%E7%8E%B0%E4%BB%A3c&#43;&#43;%E8%AF%AD%E6%B3%95/" class="next" rel="next" title="">Next Post<i class="fas fa-angle-right fa-fw"></i></a></div></div>
</div></article></div>
            </main>
            <footer class="footer"><div class="footer-container"><div class="footer-line">由 <a href="https://gohugo.io/" target="_blank" rel="noopener noreffer" title="Hugo 0.86.0">Hugo</a> 强力驱动 | 主题 - <a href="https://github.com/khusika/FeelIt" target="_blank" rel="noopener noreffer" title="FeelIt 1.0.1"><i class="fas fa-hand-holding-heart fa-fw"></i> FeelIt</a>
        </div><div class="footer-line" itemscope itemtype="http://schema.org/CreativeWork"><i class="far fa-copyright fa-fw"></i><span itemprop="copyrightYear">2023</span><span class="author" itemprop="copyrightHolder">&nbsp;<a href="/"></a></span></div>
</div>
</footer>
        </div>

        <div id="fixed-buttons"><a href="#" id="back-to-top" class="fixed-button" title="回到顶部">
                <i class="fas fa-chevron-up fa-fw"></i>
            </a></div><link rel="stylesheet" href="/lib/fontawesome-free/all.min.css"><link rel="stylesheet" href="/lib/animate/animate.min.css"><link rel="stylesheet" href="/lib/katex/katex.min.css"><link rel="stylesheet" href="/lib/katex/copy-tex.min.css"><script src="/lib/autocomplete/autocomplete.min.js"></script><script src="/lib/lunr/lunr.min.js"></script><script src="/lib/lunr/lunr.stemmer.support.min.js"></script><script src="/lib/lunr/lunr.zh.min.js"></script><script src="/lib/lazysizes/lazysizes.min.js"></script><script src="/lib/clipboard/clipboard.min.js"></script><script src="/lib/sharer/sharer.min.js"></script><script src="/lib/katex/katex.min.js"></script><script src="/lib/katex/auto-render.min.js"></script><script src="/lib/katex/copy-tex.min.js"></script><script src="/lib/katex/mhchem.min.js"></script><script>window.config={"code":{"copyTitle":"复制到剪贴板","maxShownLines":200},"comment":{},"math":{"delimiters":[{"display":true,"left":"$$","right":"$$"},{"display":true,"left":"\\[","right":"\\]"},{"display":false,"left":"$","right":"$"},{"display":false,"left":"\\(","right":"\\)"}],"strict":false},"search":{"highlightTag":"em","lunrIndexURL":"/index.json","lunrLanguageCode":"zh","lunrSegmentitURL":"/lib/lunr/lunr.segmentit.js","maxResultLength":100,"noResultsFound":"没有找到结果","snippetLength":50,"type":"lunr"}};</script><script src="/js/theme.min.js"></script></body></html>
